# -*- coding: utf-8 -*-
"""
    Time    : 2020/11/30 11:28 下午
    Author  : Thinkgamer
    File    : 004-寻找两个正序数组的中位数.py
    Desc    : https://leetcode-cn.com/problems/median-of-two-sorted-arrays
"""

"""
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

示例 3：
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000

示例 4：
输入：nums1 = [], nums2 = [1]
输出：1.00000

示例 5：
输入：nums1 = [2], nums2 = []
输出：2.00000

提示：

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-10^6 <= nums1[i], nums2[i] <= 10^6
"""


# 40 ms 87.63% / 13.1 MB 36.24%
def find_median_sorted_arrays_v1(nums1, nums2):
	# 创建一个新数组
	nums = list()
	m = nums1.__len__()
	n = nums2.__len__()
	if m+n == 0:
		return 0.
	# 下标
	i = 0
	j = 0
	while i < m and j < n:
		if nums1[i] >= nums2[j]:
			nums.append(nums2[j])
			j += 1
		else:
			nums.append(nums1[i])
			i += 1
	while i < m:
		nums.append(nums1[i])
		i += 1

	while j < n:
		nums.append(nums2[j])
		j += 1

	if (m + n) % 2 == 0:  # 长度为偶数
		return float(nums[int((m+n)/2) - 1] + nums[int((m+n)/2)]) / 2
	else:                 # 长度为奇数
		return float(nums[int((m+n)/2)])


def find_median_sorted_arrays_v2(nums1, nums2):
	# 创建一个新数组
	nums = list()
	m = len(nums1)
	n = len(nums2)
	if m + n == 0:
		return 0.
	# 下标
	i = 0
	j = 0
	while i < m and j < n:
		if nums1[i] >= nums2[j]:
			nums.append(nums2[j])
			j += 1
		else:
			nums.append(nums1[i])
			i += 1

	while i < m:
		nums.append(nums1[i])
		i += 1

	while j < n:
		nums.append(nums2[j])
		j += 1

	mid = int((m + n)/2)

	if (m + n) % 2 == 0:  # 长度为偶数
		return float(nums[mid - 1] + nums[mid]) / 2
	else:  # 长度为奇数
		return float(nums[mid])


# 56ms 32.63% | 13.2mb 24.77%
def find_median_sorted_arrays_v3(nums1, nums2):
	# 找到中心位，可能是1位或者2位，记录在middle中，非下标
	len1 = len(nums1)
	len2 = len(nums2)
	if (len1 + len2) % 2 == 0:
		temp = int((len1 + len2) / 2)
		middle = [temp, temp + 1]
	else:
		middle = [int((len1 + len2) / 2) + 1]

	i = 0
	j = 0
	# 记录目前 综合之后 是到第几位了
	ij = 0
	# 记录 middle 位对应的 value
	middle_value = []
	while i < len1 and j < len2 and len(middle) != 0:
		if nums1[i] < nums2[j]:
			i += 1
			ij += 1
			if ij in middle:
				middle_value.append(nums1[i - 1])
				middle.pop(0)
		else:
			j += 1
			ij += 1
			if ij in middle:
				middle_value.append(nums2[j - 1])
				middle.pop(0)

	while i < len1 and len(middle) != 0:
		i += 1
		ij += 1
		if ij in middle:
			middle_value.append(nums1[i - 1])
			middle.pop(0)

	while j < len2 and len(middle) != 0:
		j += 1
		ij += 1
		if ij in middle:
			middle_value.append(nums2[j - 1])
			middle.pop(0)

	return float(sum(middle_value)) / len(middle_value)


nums1 = [1, 2]
nums2 = [3, 4]
# nums1 = [1, 3]
# nums2 = [2]
# nums1 = [0, 0]
# nums2 = [0, 0]
# nums1 = []
# nums2 = [0]

result = find_median_sorted_arrays_v3(nums1, nums2)
print(result)
